package cn.lishiyuan.algorithm.sort;

import java.util.List;

/**
 * 快速排序
 * <br>
 * 快速排序的思路是，取一个元素作为分区点，将比这个小的元素放入到该元素的左边，将比这个大的元素放到这个元素右边。
 * <br>
 * 以此类推，对于每个分区的元素在分区完成后可以进行再分区，如此递归，便可实现快速排序。
 *
 */
public class QuickSort implements LeeSort{

    @Override
    public <T extends Comparable<T>> List<T> sort(List<T> data) {
        quickSort(data, 0, data.size() - 1);
        return data;
    }

    private <T extends  Comparable<T>> void quickSort(List<T> data, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = partition(data, left, right);

        quickSort(data, left, mid - 1);
        quickSort(data, mid + 1, right);
    }

    /**
     * 分区函数2
     * <br>
     * 1. 首先将取样，首，尾，中间元素中等大下坡元素作为选中的分区元素
     * <br>
     * 2. 将该元素交换到首位，也就是left位置。
     * <br>
     * 3. 使用高位high索引存储等于选中元素的最大index，使用低位low索引存储等于选中元素最小的index
     * <br>
     * 4. 遍历合集，如果当前元素大于选中元素，则将当前元素与高位元素交换，high--；如果当前元素等于选中元素，则index++。
     * 如果当前元素小于选中元素，则当前当前元素与低位交换，low++，index++；
     * <br>
     * 5. 遍历完成后low就是分区的index
     * <br>
     *
     * @param data
     * @param left
     * @param right
     * @return
     * @param <T>
     */
    private <T extends  Comparable<T>>  int partition(List <T> data, int left, int right){
        int mid = (right + left) / 2;

        int nowIndex;
        T selectItem;

        T one = data.get(left);
        T two = data.get(mid);
        T three = data.get(right);
        // 选择合适的元素
        if (one.compareTo(two) > 0) {
            if (two.compareTo(three) > 0) {
                selectItem = two;
                nowIndex = mid;
            } else if (one.compareTo(three) > 0) {
                selectItem = three;
                nowIndex = right;
            } else {
                selectItem = one;
                nowIndex = left;
            }
        } else {
            if (one.compareTo(three) > 0) {
                selectItem = one;
                nowIndex = left;
            } else if (two.compareTo(three) > 0) {
                selectItem = three;
                nowIndex = right;
            } else {
                selectItem = two;
                nowIndex = mid;
            }
        }

        // 将选中元素放入left，这相当于将首位置空，留出了一个空位。
        data.set(nowIndex, data.get(left));
        data.set(left, selectItem);

//        // 双指针
//        int low = left, high = right;
//        for (;low < high;) {
//            for (;low < high && data.get(high).compareTo(selectItem) >= 0;) {
//                high--;
//            }
//            data.set(low, data.get(high));
//
//            for (;low < high && data.get(low).compareTo(selectItem) < 0;) {
//                low++;
//            }
//            data.set(high, data.get(low));
//        }
//        // 将选中元素放回到空位
//        data.set(low, selectItem);
//        nowIndex = low;



        // 荷兰国旗算法：通过一次遍历确定区分三部分
        int low = left, high = right, i = left;
        while (i <= high) {
            if (data.get(i).compareTo(selectItem) < 0) {
                // 当前元素小于选中元素的时候，将当前元素换到低位（因为left就是选中元素的位置，所以相当于选中元素换到了当前位置）
                T temp = data.get(i);
                data.set(i, data.get(low));
                data.set(low, temp);
                low++;
                i++;
            } else if (data.get(i).compareTo(selectItem) > 0) {
                // 如果当前元素大于选中元素，将当前元素换到高位（相当于将最小的右边元素的index换到了当前位置）
                T temp = data.get(i);
                data.set(i, data.get(high));
                data.set(high, temp);
                // 注意这里是没有移动i的，也就是当前元素index，没有变化，又因为当前元素是从高位下来的，所以他会被再比较一遍
                high--;
            } else {
                i++;
            }
        }

        // low是最小的等于元素的index，high是最大的等于元素的index

        return low; // 返回等于基准的起始索引


    }


    @Override
    public <T extends Comparable<T>> T[] sort(T[] data) {
        quickSort(data, 0, data.length - 1);
        return data;
    }

    private <T extends  Comparable<T>> void quickSort(T[] data, int left, int right) {
        if (left >= right) {
            return;
        }

        int nowIndex = partition(data, left, right);

        quickSort(data, left, nowIndex - 1);
        quickSort(data, nowIndex + 1, right);
    }

    /**
     * 分区函数1
     * <br>
     * 1. 首先将取样，首，尾，中间元素中等大下坡元素作为选中的分区元素
     * <br>
     * 2. 将该元素交换到末尾，也就是right位置。
     * <br>
     * 3. 使用nowIndex记录分界点，左边是比选中元素小的，右边是比分区元素大的。默认从left开始
     * <br>
     * 4. 遍历集合，当遇到遇到比选中元素小的元素。则该元素与nowIndex元素交换位置。然后nowIndex++。
     * 这就使得nowIndex之前的元素必然是比选中元素小的。
     * <br>
     * 5. nowIndex元素与末尾元素，也就是选中元素，也就是right位置的元素交换。
     * 这样nowIndex元素必然是选中元素，nowIndex之前的元素必然比选中元素小。
     *
     * @param data
     * @param left
     * @param right
     * @return
     * @param <T>
     */
    private <T extends  Comparable<T>>  int partition(T[] data, int left, int right){
        int mid = (right + left) / 2;

        T selectItem ;
        int selectIndex ;

        T one = data[left];
        T two = data[mid];
        T three = data[right];
        // 选择合适的元素
        if (one.compareTo(two) > 0) {
            if (two.compareTo(three) > 0) {
                selectItem = two;
                selectIndex = mid;
            } else if (one.compareTo(three) > 0) {
                selectItem = three;
                selectIndex = right;
            } else {
                selectItem = one;
                selectIndex = left;
            }
        } else {
            if (one.compareTo(three) > 0) {
                selectItem = one;
                selectIndex = left;
            } else if (two.compareTo(three) > 0) {
                selectItem = three;
                selectIndex = right;
            } else {
                selectItem = two;
                selectIndex = mid;
            }
        }

        // 将选中元素交换到最右边，这相当于将末位置空，留出了一个空位。
        data[selectIndex] = data[right];
        data[right] = selectItem;

        // 遍历合集，比当前元素小的放到左边，大的放到右边 需要构建两个合集分别存小元素与大元素，这里我们原地分区
        // 大小元素的分界点
        int nowIndex = left;

        for (int i = left ; i <= (right -1); i++) {
            if (data[i].compareTo(selectItem) < 0) {
                // 当前元素比选中元素小，
                T temp = data[nowIndex];
                data[nowIndex] = data[i];
                data[i] = temp;
                nowIndex++;
            }
        }

        // 将选中元素放入分界线
        T temp = data[nowIndex];
        data[nowIndex] = data[right];
        data[right] = temp;

        return nowIndex;
    }

}
